{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delivering Boxes from Storage to Ports"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #segment-tree #queue #array #dynamic-programming #prefix-sum #monotonic-queue #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #线段树 #队列 #数组 #动态规划 #前缀和 #单调队列 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: boxDelivering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从仓库到码头运输箱子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有&nbsp;<strong>箱子数目的限制</strong>&nbsp;和 <strong>总重量的限制</strong>&nbsp;。</p>\n",
    "\n",
    "<p>给你一个箱子数组&nbsp;<code>boxes</code>&nbsp;和三个整数 <code>portsCount</code>, <code>maxBoxes</code>&nbsp;和&nbsp;<code>maxWeight</code>&nbsp;，其中&nbsp;<code>boxes[i] = [ports<sub>​​i</sub>​, weight<sub>i</sub>]</code>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>ports<sub>​​i</sub></code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个箱子需要送达的码头，&nbsp;<code>weights<sub>i</sub></code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个箱子的重量。</li>\n",
    "\t<li><code>portsCount</code>&nbsp;是码头的数目。</li>\n",
    "\t<li><code>maxBoxes</code> 和&nbsp;<code>maxWeight</code>&nbsp;分别是卡车每趟运输箱子数目和重量的限制。</li>\n",
    "</ul>\n",
    "\n",
    "<p>箱子需要按照 <strong>数组顺序</strong>&nbsp;运输，同时每次运输需要遵循以下步骤：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>卡车从&nbsp;<code>boxes</code>&nbsp;队列中按顺序取出若干个箱子，但不能违反&nbsp;<code>maxBoxes</code> 和&nbsp;<code>maxWeight</code>&nbsp;限制。</li>\n",
    "\t<li>对于在卡车上的箱子，我们需要 <strong>按顺序</strong>&nbsp;处理它们，卡车会通过 <strong>一趟行程</strong>&nbsp;将最前面的箱子送到目的地码头并卸货。如果卡车已经在对应的码头，那么不需要 <strong>额外行程</strong>&nbsp;，箱子也会立马被卸货。</li>\n",
    "\t<li>卡车上所有箱子都被卸货后，卡车需要 <strong>一趟行程</strong>&nbsp;回到仓库，从箱子队列里再取出一些箱子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>卡车在将所有箱子运输并卸货后，最后必须回到仓库。</p>\n",
    "\n",
    "<p>请你返回将所有箱子送到相应码头的&nbsp;<b>最少行程</b>&nbsp;次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>最优策略如下：\n",
    "- 卡车将所有箱子装上车，到达码头 1 ，然后去码头 2 ，然后再回到码头 1 ，最后回到仓库，总共需要 4 趟行程。\n",
    "所以总行程数为 4 。\n",
    "注意到第一个和第三个箱子不能同时被卸货，因为箱子需要按顺序处理（也就是第二个箱子需要先被送到码头 2 ，然后才能处理第三个箱子）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>最优策略如下：\n",
    "- 卡车首先运输第一个箱子，到达码头 1 ，然后回到仓库，总共 2 趟行程。\n",
    "- 卡车运输第二、第三、第四个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。\n",
    "- 卡车运输第五个箱子，到达码头 2 ，回到仓库，总共 2 趟行程。\n",
    "总行程数为 2 + 2 + 2 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>最优策略如下：\n",
    "- 卡车运输第一和第二个箱子，到达码头 1 ，然后回到仓库，总共 2 趟行程。\n",
    "- 卡车运输第三和第四个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。\n",
    "- 卡车运输第五和第六个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。\n",
    "总行程数为 2 + 2 + 2 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>boxes = [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]], portsCount = 5, maxBoxes = 5, maxWeight = 7\n",
    "<b>输出：</b>14\n",
    "<b>解释：</b>最优策略如下：\n",
    "- 卡车运输第一个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。\n",
    "- 卡车运输第二个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。\n",
    "- 卡车运输第三和第四个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。\n",
    "- 卡车运输第五个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。\n",
    "- 卡车运输第六和第七个箱子，到达码头 3 ，然后去码头 4 ，然后回到仓库，总共 3 趟行程。\n",
    "- 卡车运输第八和第九个箱子，到达码头 1 ，然后去码头 5 ，然后回到仓库，总共 3 趟行程。\n",
    "总行程数为 2 + 2 + 2 + 2 + 3 + 3 = 14 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= boxes.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= portsCount, maxBoxes, maxWeight &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= ports<sub>​​i</sub> &lt;= portsCount</code></li>\n",
    "\t<li><code>1 &lt;= weights<sub>i</sub> &lt;= maxWeight</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delivering-boxes-from-storage-to-ports](https://leetcode.cn/problems/delivering-boxes-from-storage-to-ports/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delivering-boxes-from-storage-to-ports](https://leetcode.cn/problems/delivering-boxes-from-storage-to-ports/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[2,1],[1,1]]\\n2\\n3\\n3', '[[1,2],[3,3],[3,1],[3,1],[2,4]]\\n3\\n3\\n6', '[[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]]\\n3\\n6\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n = len(boxes)\n",
    "        w, c = [0] * (n + 1), [0] * n\n",
    "        for i in range(n):\n",
    "            w[i + 1] = w[i] + boxes[i][1]\n",
    "            if i != 0: c[i] = c[i - 1] + (1 if boxes[i][0] != boxes[i - 1][0] else 0)\n",
    "        q,f=deque(),[0]*(n+1)\n",
    "        q.append(0)\n",
    "        for i in range(1,n+1):\n",
    "            while q and (i-q[0]>maxBoxes or w[i]-w[q[0]]>maxWeight): q.popleft()\n",
    "            if q:f[i]=c[i-1]+f[q[0]]-c[q[0]]+2\n",
    "            while q and i<n and f[q[-1]]-c[q[-1]]>=f[i]-c[i]:q.pop()\n",
    "            q.append(i)\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n = len(boxes)\n",
    "        w, c = [0] * (n + 1), [0] * n\n",
    "        for i in range(n):\n",
    "            w[i + 1] = w[i] + boxes[i][1]\n",
    "            if i != 0: c[i] = c[i - 1] + (1 if boxes[i][0] != boxes[i - 1][0] else 0)\n",
    "        q,f=deque(),[0]*(n+1)\n",
    "        q.append(0)\n",
    "        for i in range(1,n+1):\n",
    "            while q and (i-q[0]>maxBoxes or w[i]-w[q[0]]>maxWeight): q.popleft()\n",
    "            if q:f[i]=c[i-1]+f[q[0]]-c[q[0]]+2\n",
    "            while q and i<n and f[q[-1]]-c[q[-1]]>=f[i]-c[i]:q.pop()\n",
    "            q.append(i)\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n = len(boxes)\n",
    "        w, c = [0] * (n + 1), [0] * n\n",
    "        for i in range(n):\n",
    "            w[i + 1] = w[i] + boxes[i][1]\n",
    "            if i != 0: c[i] = c[i - 1] + (1 if boxes[i][0] != boxes[i - 1][0] else 0)\n",
    "        q,f=deque(),[0]*(n+1)\n",
    "        q.append(0)\n",
    "        for i in range(1,n+1):\n",
    "            while q and (i-q[0]>maxBoxes or w[i]-w[q[0]]>maxWeight): q.popleft()\n",
    "            if q:f[i]=c[i-1]+f[q[0]]-c[q[0]]+2\n",
    "            while q and f[q[-1]]-c[q[-1]]>=f[i]-c[i-1]:q.pop()\n",
    "            q.append(i)\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n = len(boxes)\n",
    "\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[n] = 0\n",
    "\n",
    "        suf_w = [0] * (n + 1)\n",
    "        suf_cnt = [0] * (n + 1)\n",
    "\n",
    "        for k in range(n - 1, -1, -1):\n",
    "            suf_w[k] = suf_w[k + 1] + boxes[k][1]\n",
    "\n",
    "            if k > 0 and boxes[k][0] != boxes[k - 1][0]:\n",
    "                suf_cnt[k] = suf_cnt[k + 1] + 1\n",
    "            else:\n",
    "                suf_cnt[k] = suf_cnt[k + 1]\n",
    "\n",
    "        q = deque([(n, 0)])\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # for k in range(i, n):\n",
    "            #     if suf_w[i] - suf_w[k + 1] <= maxWeight and k  + 1 - i <= maxBoxes:\n",
    "            #         dp[i] = min(dp[i], dp[k + 1] - suf_cnt[k + 1] + suf_cnt[i + 1] + 2)\n",
    "            #         print(k + 1, dp[k + 1] - suf_cnt[k + 1])\n",
    "\n",
    "            while q and (q[0][0] - i > maxBoxes or suf_w[i] - suf_w[q[0][0]] > maxWeight):\n",
    "                q.popleft()\n",
    "\n",
    "            # print(i, q, suf_w[i] - suf_w[q[0][0]])\n",
    "            \n",
    "            dp[i] = q[0][1] + suf_cnt[i + 1] + 2\n",
    "\n",
    "            while q and q[-1][1] >= dp[i] - suf_cnt[i]:\n",
    "                q.pop()\n",
    "\n",
    "            q.append((i, dp[i] - suf_cnt[i]))\n",
    "\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        dic = dict()\n",
    "        lb = len(boxes)\n",
    "        weights = [0] * (lb + 1)\n",
    "        w = 0\n",
    "        for i in range(lb):\n",
    "            w += boxes[i][1]\n",
    "            weights[i + 1] = w\n",
    "        negs = [0] * (lb + 1)\n",
    "        neg = 0\n",
    "        h = boxes[0][0]\n",
    "        for i in range(lb):\n",
    "            if h != boxes[i][0]:\n",
    "                h = boxes[i][0]\n",
    "                neg += 1\n",
    "            negs[i + 1] = neg\n",
    "        dp = [0] * (lb + 1)\n",
    "        q = deque([0]) # 满足条件的序号队列\n",
    "        g = [0] * (lb + 1)\n",
    "        for i in range(1, lb + 1):\n",
    "            while i - q[0] > maxBoxes or weights[i] - weights[q[0]] > maxWeight:\n",
    "                q.popleft()\n",
    "            dp[i] = g[q[0]] + negs[i] + 2\n",
    "            if i < lb:\n",
    "                g[i] = dp[i] - negs[i + 1]\n",
    "                while q and g[q[-1]] >= g[i]:\n",
    "                    q.pop()\n",
    "                q.append(i)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n=len(boxes)\n",
    "        dp=[0]*n       \n",
    "        diff=[0]*n\n",
    "        diff[0]=1\n",
    "        for i in range(1,n):\n",
    "            if boxes[i][0]!=boxes[i-1][0]:\n",
    "                diff[i]=1\n",
    "        \n",
    "        dp[0]=2\n",
    "        pw=boxes[0][1]\n",
    "        # [(shipweight,shipbox,cost)]\n",
    "        window=[(boxes[0][1],1,2)]      \n",
    "        #window 每次增加从这个位置 i 新跑的一趟  \n",
    "        for i in range(1,n):\n",
    "            nextwindow=[(boxes[i][1],1,2+dp[i-1])]\n",
    "            ans=dp[i-1]+2\n",
    "            while window:\n",
    "                winweight,winbox,precost=window.pop()\n",
    "                winweight+=boxes[i][1]\n",
    "                winbox+=1\n",
    "                precost+=diff[i]\n",
    "                if winweight>maxWeight:\n",
    "                    continue\n",
    "                if winbox>maxBoxes:\n",
    "                    continue\n",
    "                if precost<ans:\n",
    "                    ans=precost\n",
    "                    nextwindow.append((winweight,winbox,precost))\n",
    "            dp[i]=ans\n",
    "            window=nextwindow[::-1]\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n = len(boxes)\n",
    "        w = list(accumulate([x[1] for x in boxes], initial=0))\n",
    "        c = list(accumulate([a!=b for a,b in pairwise([x[0] for x in boxes])],initial=0))\n",
    "        q,f=deque([0]),[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            while q and (i-q[0]>maxBoxes or w[i]-w[q[0]]>maxWeight): q.popleft()\n",
    "            if q:f[i]=c[i-1]+f[q[0]]-c[q[0]]+2\n",
    "            while q and i<n and f[q[-1]]-c[q[-1]]>=f[i]-c[i]:q.pop()\n",
    "            q.append(i)\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n = len(boxes)\n",
    "        ws = list(accumulate((box[1] for box in boxes), initial=0))\n",
    "        c = [int(a != b) for a, b in pairwise(box[0] for box in boxes)]\n",
    "        cs = list(accumulate(c, initial=0))\n",
    "        f = [0] * (n + 1)\n",
    "        q = deque([0])\n",
    "        for i in range(1, n + 1):\n",
    "            while q and (i - q[0] > maxBoxes or ws[i] - ws[q[0]] > maxWeight):\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                f[i] = cs[i - 1] + f[q[0]] - cs[q[0]] + 2\n",
    "            if i < n:\n",
    "                while q and f[q[-1]] - cs[q[-1]] >= f[i] - cs[i]:\n",
    "                    q.pop()\n",
    "                q.append(i)\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n = len(boxes)\n",
    "        ws = list(accumulate((box[1] for box in boxes),initial = 0))\n",
    "        c = [int(a!=b) for a,b in pairwise(box[0] for box in boxes)]\n",
    "        cs = list(accumulate(c,initial=0))\n",
    "        f = [inf] * (n+1)\n",
    "        f[0] = 0\n",
    "        q = deque([0])\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            while q and (i-q[0]>maxBoxes or ws[i]-ws[q[0]] > maxWeight):\n",
    "                q.popleft()\n",
    "            \n",
    "            if q:\n",
    "                f[i] = cs[i-1] + f[q[0]] - cs[q[0]] + 2\n",
    "            if i<n:\n",
    "                while q and f[q[-1]] - cs[q[-1]] >= f[i] - cs[i]:\n",
    "                    q.pop()\n",
    "                q.append(i)\n",
    "\n",
    "        return f[n]\n",
    "\n",
    "\n",
    "#\n",
    "# maxBoxes    maxWeight    \n",
    "# 箱子的状态：在第i轮被装上车  第i轮的第j类箱子(前一轮回到起点的行程总数+j)\n",
    "# 一直到第n个箱子的最优解  min\n",
    "#\n",
    "# 第i轮 遍历每一个可能的窗口大小，窗口大小从0到min(maxBoxes,sum(l,r)weight <= maxWeight)\n",
    "# f[i][l][r]\n",
    "#\n",
    "#\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n=len(boxes)\n",
    "        dp=[0]*n       \n",
    "        diff=[0]*n\n",
    "        diff[0]=1\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if boxes[i][0]!=boxes[i-1][0]:\n",
    "                diff[i]=1\n",
    "        # [ports​​i​, weighti]\n",
    "        \n",
    "        dp[0]=2\n",
    "        window=[]\n",
    "        if boxes[0][1]<maxWeight:\n",
    "            window.append((boxes[0][1],0,1))\n",
    "        #window may not need all\n",
    "        #compare min dp[s-1]-port[s-1]+port[j],\n",
    "        for i in range(1,n):\n",
    "            nextwindow=[]\n",
    "            ans=dp[i-1]+2\n",
    "            for win in window:\n",
    "                pw,start,ports=win\n",
    "                pw+=boxes[i][1]\n",
    "                ports+=diff[i]   \n",
    "                if pw>maxWeight:\n",
    "                    continue                           \n",
    "                if ports>maxBoxes:\n",
    "                    continue \n",
    "                travel=ports\n",
    "                if start>0:\n",
    "                    travel+=dp[start-1]\n",
    "                while nextwindow:\n",
    "                    nw,nstart,nport=nextwindow[-1]\n",
    "                    ntravel=nport\n",
    "                    if nstart>0:\n",
    "                        ntravel+=dp[nstart-1]\n",
    "                    if ntravel>=travel:\n",
    "                        nextwindow.pop()\n",
    "                    else:\n",
    "                        break\n",
    "                travel+=1\n",
    "                if travel<ans:\n",
    "                    ans=travel \n",
    "                nextwindow.append((pw,start,ports))            \n",
    "            nextwindow.append((boxes[i][1],i,1))\n",
    "            window=nextwindow\n",
    "            dp[i]=ans\n",
    "      \n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n = len(boxes)\n",
    "        s = [0] * (n + 2)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            s[i] = s[i - 1]\n",
    "            if i == 1 or boxes[i - 1][0] != boxes[i - 2][0]:\n",
    "                s[i] += 1\n",
    "        \n",
    "        def cost(l, r):\n",
    "            if s[l] == s[l + 1]:\n",
    "                return s[r] - s[l] + 1\n",
    "            return s[r] - s[l]\n",
    "        \n",
    "        q = deque([0])\n",
    "        w = 0\n",
    "        j = 1\n",
    "        for i in range(1, n + 1):\n",
    "            w += boxes[i - 1][1]\n",
    "            while q and w > maxWeight or i - j + 1 > maxBoxes:\n",
    "                w -= boxes[j - 1][1]\n",
    "                j += 1\n",
    "            while q[0] < j - 1:\n",
    "                q.popleft()\n",
    "            k = q[0]\n",
    "            f[i] = f[k] + cost(k, i) + 1\n",
    "            while q and f[q[-1]] >= f[i] + cost(i, i + 1) - cost(q[-1], i + 1) :\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "\n",
    "        return f[n]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n=len(boxes)\n",
    "        dp=[0]*n       \n",
    "        diff=[0]*n\n",
    "        diff[0]=1\n",
    "        for i in range(1,n):\n",
    "            if boxes[i][0]!=boxes[i-1][0]:\n",
    "                diff[i]=1\n",
    "        \n",
    "        dp[0]=2\n",
    "        pw=boxes[0][1]\n",
    "        # [(shipweight,shipbox,cost)]\n",
    "        window=[(boxes[0][1],1,2)]      \n",
    "        #window 每次增加从这个位置 i 新跑的一趟  \n",
    "        for i in range(1,n):\n",
    "            nextwindow=[(boxes[i][1],1,2+dp[i-1])]\n",
    "            ans=dp[i-1]+2\n",
    "            for j in range(len(window)):\n",
    "                winweight,winbox,precost=window[j]\n",
    "                winweight+=boxes[i][1]\n",
    "                winbox+=1\n",
    "                precost+=diff[i]\n",
    "                if winweight>maxWeight:\n",
    "                    continue\n",
    "                if winbox>maxBoxes:\n",
    "                    continue\n",
    "                if precost<ans:\n",
    "                    ans=precost\n",
    "                    nextwindow.append((winweight,winbox,precost))\n",
    "            dp[i]=ans\n",
    "            window=nextwindow\n",
    "        # print(dp)\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n=len(boxes)\n",
    "        dp=[0]*n       \n",
    "        diff=[0]*n\n",
    "        diff[0]=1\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if boxes[i][0]!=boxes[i-1][0]:\n",
    "                diff[i]=1\n",
    "        # [ports​​i​, weighti]\n",
    "        \n",
    "        dp[0]=2\n",
    "        window=[]\n",
    "        if boxes[0][1]<maxWeight:\n",
    "            window.append((boxes[0][1],0,1))\n",
    "        #window may not need all\n",
    "        #compare min dp[s-1]-port[s-1]+port[j],\n",
    "        for i in range(1,n):\n",
    "            nextwindow=[]\n",
    "            ans=dp[i-1]+2\n",
    "            for win in window:\n",
    "                pw,start,ports=win\n",
    "                pw+=boxes[i][1]\n",
    "                ports+=diff[i]   \n",
    "                if pw>maxWeight:\n",
    "                    continue                           \n",
    "                if ports>maxBoxes:\n",
    "                    continue \n",
    "                travel=ports\n",
    "                if start>0:\n",
    "                    travel+=dp[start-1]\n",
    "                while nextwindow:\n",
    "                    nw,nstart,nport=nextwindow.pop()\n",
    "                    ntravel=nport\n",
    "                    if nstart>0:\n",
    "                        ntravel+=dp[nstart-1]\n",
    "                    if ntravel>=travel:\n",
    "                        continue\n",
    "                    else:\n",
    "                        nextwindow.append((nw,nstart,nport))\n",
    "                        break\n",
    "                travel+=1\n",
    "                if travel<ans:\n",
    "                    ans=travel \n",
    "                nextwindow.append((pw,start,ports))            \n",
    "            nextwindow.append((boxes[i][1],i,1))\n",
    "            window=nextwindow\n",
    "            dp[i]=ans\n",
    "      \n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n=len(boxes)\n",
    "        dp=[0]*n       \n",
    "        diff=[0]*n\n",
    "        diff[0]=1\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if boxes[i][0]!=boxes[i-1][0]:\n",
    "                diff[i]=1\n",
    "        # [ports​​i​, weighti]\n",
    "        \n",
    "        dp[0]=2\n",
    "        window=[]\n",
    "        if boxes[0][1]<maxWeight:\n",
    "            window.append((boxes[0][1],0,1))\n",
    "        #window may not need all\n",
    "        #compare min dp[s-1]-port[s-1]+port[j],\n",
    "        for i in range(1,n):\n",
    "            nextwindow=[]\n",
    "            ans=dp[i-1]+2\n",
    "            for win in window:\n",
    "                pw,start,ports=win\n",
    "                pw+=boxes[i][1]\n",
    "                ports+=diff[i]   \n",
    "                if pw>maxWeight:\n",
    "                    continue                           \n",
    "                if ports>maxBoxes:\n",
    "                    continue \n",
    "                travel=ports\n",
    "                if start>0:\n",
    "                    travel+=dp[start-1]\n",
    "                while nextwindow:\n",
    "                    nw,nstart,nport=nextwindow.pop()\n",
    "                    ntravel=nport\n",
    "                    if nstart>0:\n",
    "                        ntravel+=dp[nstart-1]\n",
    "                    if ntravel>=travel:\n",
    "                        continue\n",
    "                    else:\n",
    "                        nextwindow.append((nw,nstart,nport))\n",
    "                        break\n",
    "                travel+=1\n",
    "                if travel<ans:\n",
    "                    ans=travel \n",
    "                nextwindow.append((pw,start,ports))\n",
    "            if boxes[i][1]<maxWeight:\n",
    "                # while nextwindow:\n",
    "                #     if nextwindow[-1][2]>=1:\n",
    "                #         nextwindow.pop()\n",
    "                #     else:\n",
    "                #         break\n",
    "                nextwindow.append((boxes[i][1],i,1))\n",
    "            window=nextwindow\n",
    "            dp[i]=ans\n",
    "      \n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n = len(boxes)\n",
    "        ports, weights = [], []\n",
    "        for p, w in boxes:\n",
    "            ports.append(p)\n",
    "            weights.append(w)\n",
    "        ws = list(accumulate(weights, initial=0))\n",
    "        c = [int(a != b) for a, b in pairwise(ports)]\n",
    "        cs = list(accumulate(c, initial=0))\n",
    "        q = deque([0])\n",
    "        f = [0] + [inf] * n\n",
    "        for i in range(1, n + 1):\n",
    "            while q and (i - q[0] > maxBoxes or ws[i] - ws[q[0]] > maxWeight):\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                f[i] = cs[i - 1] + f[q[0]] - cs[q[0]] + 2\n",
    "            if i < n:\n",
    "                while q and f[q[-1]] - cs[q[-1]] >= f[i] - cs[i]:\n",
    "                    q.pop()\n",
    "                q.append(i)\n",
    "        return f[n]\n",
    "\n",
    "        # n = len(boxes)\n",
    "        # ports, weights = [], []\n",
    "        # for p, w in boxes:\n",
    "        #     ports.append(p)\n",
    "        #     weights.append(w)\n",
    "        # ws = list(accumulate(weights, initial=0))\n",
    "        # c = [int(a != b) for a, b in pairwise(ports)]\n",
    "        # cs = list(accumulate(c, initial=0))     \n",
    "        # f = [0] + [inf] * n\n",
    "        # for i in range(1, n + 1):\n",
    "        #     for j in range(max(0, i - maxBoxes), i):\n",
    "        #         if ws[i] - ws[j] <= maxWeight:\n",
    "        #             f[i] = min(f[i], f[j] + cs[i - 1] - cs[j] + 2)\n",
    "        # return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n=len(boxes)\n",
    "        dp=[0]*n       \n",
    "        diff=[0]*n\n",
    "        diff[0]=1\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if boxes[i][0]!=boxes[i-1][0]:\n",
    "                diff[i]=1\n",
    "        # [ports​​i​, weighti]\n",
    "        \n",
    "        dp[0]=2\n",
    "        window=[]\n",
    "        if boxes[0][1]<maxWeight:\n",
    "            window.append((boxes[0][1],0,1))\n",
    "        #window may not need all\n",
    "        #compare min dp[s-1]-port[s-1]+port[j],\n",
    "        for i in range(1,n):\n",
    "            nextwindow=[]\n",
    "            ans=dp[i-1]+2\n",
    "            for win in window:\n",
    "                pw,start,ports=win\n",
    "                pw+=boxes[i][1]\n",
    "                ports+=diff[i]   \n",
    "                if pw>maxWeight:\n",
    "                    continue                           \n",
    "                if ports>maxBoxes:\n",
    "                    continue \n",
    "                travel=ports\n",
    "                if start>0:\n",
    "                    travel+=dp[start-1]\n",
    "                while nextwindow:\n",
    "                    nw,nstart,nport=nextwindow.pop()\n",
    "                    ntravel=nport\n",
    "                    if nstart>0:\n",
    "                        ntravel+=dp[nstart-1]\n",
    "                    if ntravel>=travel:\n",
    "                        continue\n",
    "                    else:\n",
    "                        nextwindow.append((nw,nstart,nport))\n",
    "                        break\n",
    "                nextwindow.append((pw,start,ports))\n",
    "                travel+=1\n",
    "                if travel<ans:\n",
    "                    ans=travel \n",
    "                nextwindow.append((pw,start,ports))\n",
    "            if boxes[i][1]<maxWeight:\n",
    "                # while nextwindow:\n",
    "                #     if nextwindow[-1][2]>=1:\n",
    "                #         nextwindow.pop()\n",
    "                #     else:\n",
    "                #         break\n",
    "                nextwindow.append((boxes[i][1],i,1))\n",
    "            window=nextwindow\n",
    "            dp[i]=ans\n",
    "      \n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n=len(boxes)\n",
    "        dp=[0]*n       \n",
    "        diff=[0]*n\n",
    "        diff[0]=1\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if boxes[i][0]!=boxes[i-1][0]:\n",
    "                diff[i]=1\n",
    "        # [ports​​i​, weighti]\n",
    "        \n",
    "        dp[0]=2\n",
    "        window=[]\n",
    "        if boxes[0][1]<maxWeight:\n",
    "            window.append((boxes[0][1],0,1))\n",
    "        #window may not need all\n",
    "        #compare min dp[s-1]-port[s-1]+port[j],\n",
    "        for i in range(1,n):\n",
    "            nextwindow=[]\n",
    "            ans=dp[i-1]+2\n",
    "            print(window)\n",
    "            for win in window:\n",
    "                pw,start,ports=win\n",
    "                pw+=boxes[i][1]\n",
    "                ports+=diff[i]   \n",
    "                if pw>maxWeight:\n",
    "                    continue                           \n",
    "                if ports>maxBoxes:\n",
    "                    continue \n",
    "                travel=ports\n",
    "                if start>0:\n",
    "                    travel+=dp[start-1]\n",
    "                while nextwindow:\n",
    "                    nw,nstart,nport=nextwindow[-1]\n",
    "                    ntravel=nport\n",
    "                    if nstart>0:\n",
    "                        ntravel+=dp[nstart-1]\n",
    "                    if ntravel>=travel:\n",
    "                        nextwindow.pop()\n",
    "                    else:\n",
    "                        break\n",
    "                travel+=1\n",
    "                if travel<ans:\n",
    "                    ans=travel \n",
    "                nextwindow.append((pw,start,ports))            \n",
    "            nextwindow.append((boxes[i][1],i,1))\n",
    "            window=nextwindow\n",
    "            dp[i]=ans\n",
    "      \n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boxDelivering(self, nums: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 2)\n",
    "        for i in range(1, n + 1):\n",
    "            s[i] = s[i - 1]\n",
    "            if i == 1 or nums[i - 1][0] != nums[i - 2][0]:\n",
    "                s[i] += 1\n",
    "        print(s)\n",
    "        def cost(l, r):\n",
    "            if s[l] == s[l + 1]:\n",
    "                return s[r] - s[l] + 1\n",
    "            return s[r] - s[l]\n",
    "\n",
    "        q = deque([0])\n",
    "        f = [0] * (n + 1)\n",
    "        w = 0\n",
    "        j = 1\n",
    "        for i in range(1, n + 1):\n",
    "            w += nums[i - 1][1]\n",
    "            while q and w > maxWeight or i - j + 1 > maxBoxes:\n",
    "                w -= nums[j - 1][1]\n",
    "                j += 1\n",
    "            while q[0] < j - 1:\n",
    "                q.popleft()\n",
    "            k = q[0]\n",
    "            # print(k, f[i])\n",
    "            f[i] = f[k] + cost(k, i) + 1\n",
    "            # print(q[-1], i + 1)\n",
    "            # while q and f[q[-1]] + cost(q[-1], i + 1) - cost(i, i + 1) >= f[i]:\n",
    "            while q and f[q[-1]] >= f[i] + cost(i, i + 1) - cost(q[-1], i + 1):\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return f[n]\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
